package sliding_window

/*
1234.有一个只含有'Q', 'W', 'E','R'四种字符，且长度为 n的字符串。
假如在该字符串中，这四个字符【都恰好】出现n/4次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

示例 1：
输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。

示例 2：
输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：
输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。

示例 4：
输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
*/

/*
One pass the all frequency of "QWER".
Then slide the windon in the string s.

Imagine that we erase all character inside the window,
as we can modyfy it whatever we want,
and it will always increase the count outside the window.

So we can make the whole string balanced,
as long as max(count[Q],count[W],count[E],count[R]) <= n / 4.

*/
func balancedString(s string) int {
	left, right, n := 0, 0, len(s)
	res, k := n, n/4
	count := [128]int{}

	for i := 0; i < n; i++ { //E.g s = QWQWERQW,n = 8, K = n/4 = 2,{Q=3, W=3, E=1, R=1}
		count[s[i]]++
	}

	// expand window
	for right < len(s) { //When right = 1 [Q] - count outside window {Q=2, W=3, E=1, R=1},right = 2 [Q,W] - count outside window {Q=2, W=2, E=1, R=1}
		c := s[right]
		count[c]--

		// shrink window: the count of each character outside the window is less than equal to K
		// then we can replace the elements inside the window with the missing characters
		// it does not matter what characters are inside the window
		for left < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k {
			d := s[left]
			count[d]++
			res = min(res, right-left+1)
			left++ // replace the elements inside
		}

		// if the count of any of the character outside the window is more than K
		// then no matter what you put inside the window ,it will still remain unbalanced

		right++
	}

	return res
}
